This invention relates generally to memory systems for computers and more particularly to cache organizations for virtual to physical address translation.
Virtual memory is an addressing scheme used in computer architectures to provide a computer programmer with a significantly larger address space than is physically present in the computer. Portions of the virtual memory space are mapped to portions of the physical memory space by way of a virtual-to-physical address translation. This translation is typically accomplished by a page table which, for a given virtual page number, produces a corresponding physical page number. This translation scheme requires the physical memory to be broken up into discrete portions or so-called pages. Pages of virtual memory can then be brought into the physical address space as needed by the operating system.
The selection of a page size involves a tradeoff. The smaller the pages the greater number of entries are required in the page table. As a result, more memory is consumed by the page table. Typically, this page table must be present in memory at all times. Making the pages larger, however, results in internal fragmentation when the program does not require all of the memory space of a given page. In addition, larger page sizes consume more I/O bandwidth and increase a process start-up time.
A technique that has been proposed for balancing these tradeoffs is providing variable page sizes. Typically, this technique allows the operating system to specify a different page size for a given process. The entries in the page table for the given process are then modified accordingly to reflect the change in the page size. Variable page sizes have a significant impact on the cache that is used to store the virtual-to-physical address translations. An example of a translation look-aside buffer used to store virtual-to-physical addresses is shown in FIG. 1. That TLB has a fixed-length tag stored in a content addressable memory (CAM). Varying the page size affects the number of bits that are required to be stored in the content addressable memory.
One approach to caching address translations for variable length pages is described in U.S. Pat. No. 5,465,337 issued to Kong, which discloses a memory management unit (MMU) for variable page sizes that includes a translation look-aside buffer (TLB) that accommodates the variable page sizes. The Kong TLB includes a plurality of entries, as with any TLB. Each entry includes a size field for specifying the size of the corresponding virtual page, a fixed virtual page field corresponding to the largest virtual page size, a variable length field that appends a variable number of bits to the fixed virtual page field depending on the specified size of the virtual page, and a corresponding physical address field. The MMU also includes means for comparing the correct number of bits of the variable length page number comprised of the fixed and variable length fields with a corresponding number of upper address bits in the upper address to identify whether there is a hit or miss in the TLB. If there is a hit, the TLB provides the corresponding physical address, which is then combined with an offset of the virtual address to form the complete physical address. One problem with the Kong approach is that each TLB entry includes unused bits for all but the smallest page size. Thus, the expensive TLB, both in terms of silicon area and manufacturing cost, is underutilized. Another disadvantage of Kong is that the entire page must be brought into memory and swapped out of memory at a time, regardless of how much will actually be required.
Accordingly, a need remains for a memory management scheme that does not suffer from the above-identified limitations.